package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * (A卷,200分)- 最多等和不相交连续子序列（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 给定一个数组，我们称其中连续的元素为连续子序列，称这些元素的和为连续子序列的和。数组中可能存在几组连续子序列，组内的连续子序列互不相交且有相同的和。求一组连续子序列，组内子序列的数目最多。输出这个数目。
 * <p>
 * 输入描述:
 * <p>
 * 第一行输入为数组长度 N，1 <= N <= 10^3.
 * 第二行为 N 个用空格分开的整数 Ci，-10^5 <= Ci <= 10^5.
 * <p>
 * 输出描述:
 * <p>
 * 第一行是一个整数 M，表示满足要求的最多的组内子序列的数目。
 * <p>
 * 示例1
 * <p>
 * 输入:
 * 10
 * <p>
 * 8 8 9 1 9 6 3 9 1 0
 * 输出:
 * <p>
 * 4
 * <p>
 * 说明:
 * 四个子序列的第一个元素和最后一个元素的下标分别为:
 * <p>
 * 2 2
 * <p>
 * 4 4
 * <p>
 * 5 6
 * <p>
 * 7 7
 * <p>
 * 示例2
 * <p>
 * 输入:
 * 10
 * <p>
 * -1 0 4 -3 6 5 -6 5 -7 -3
 * 输出:
 * 3
 * <p>
 * 说明:
 * 三个子序列的第一个元素和最后一个元素的下标分别为:
 * <p>
 * 3 3
 * <p>
 * 5 8
 * <p>
 * 9 9
 */
public class MaximumNonoverlappingConsecutiveSubsequences {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }*/

        int n = 10;
        int[] arr = Arrays.stream("8 8 9 1 9 6 3 9 1 0".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(arr, n));
        System.out.println(getResult2(arr, n));
    }

    /**
     * 前缀和数组
     *
     * @param arr
     * @param n
     * @return
     */
    public static int getResult(int[] arr, int n) {
        // 记录相同和连续子序列的区间
        HashMap<Integer, ArrayList<Integer[]>> ranges = new HashMap<>();

        // 求解arr数组的前缀和数组dp
        int[] dp = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            dp[i] = dp[i - 1] + arr[i - 1];
        }
        for (int l = 0; l < n; l++) {
            for (int r = l + 1; r < n + 1; r++) { // L R 前闭后开
                int sum = dp[r] - dp[l];
                ranges.putIfAbsent(sum, new ArrayList<>());
                ranges.get(sum).add(new Integer[]{l, r - 1});
            }
        }

        // 保存相同和不相交连续子序列的最大个数
        return ranges.entrySet().stream()
                .mapToInt(entry -> disjoint(entry.getValue()))
                .max()
                .getAsInt();
    }

    /**
     * 求不相交区间的最大个数 - 贪心
     *
     * @param ranges
     * @return
     */
    public static int disjoint(ArrayList<Integer[]> ranges) {
        int count = 1; // 至少一个
        ranges.sort((a, b) -> a[1] - b[1]); // 升序排序

        Integer t = ranges.get(0)[1];
        for (int i = 1; i < ranges.size(); i++) {
            Integer[] range = ranges.get(i);
            Integer l = range[0];
            Integer r = range[1];

            if (t < l) {
                count++;
                t = r;
            }
        }
        return count;
    }

    /**
     * 解法二
     *
     * @param arr
     * @param n
     * @return
     */
    private static int getResult2(int[] arr, int n) {
        // 记录相同和连续子序列的区间
        HashMap<Integer, ArrayList<Integer[]>> ranges = new HashMap<>();

        // 求解arr数组的前缀和数组dp
        int[] dp = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            dp[i] = dp[i - 1] + arr[i - 1];
        }
        for (int l = 0; l < n; l++) {
            for (int r = l + 1; r < n + 1; r++) { // L R 前闭后开
                int sum = dp[r] - dp[l];
                ranges.putIfAbsent(sum, new ArrayList<>());
                ranges.get(sum).add(new Integer[]{l, r - 1});
            }
        }

        // 保存相同和不相交连续子序列的最大个数
        return ranges.entrySet().stream()
                .mapToInt(entry -> eraseOverlapIntervals(entry.getValue()))
                .max()
                .getAsInt();
    }

    /**
     * 动态规划（有点类似Leetcode300-最长递增子序列）
     *
     * @param intervals
     * @return
     */
    public static int eraseOverlapIntervals(ArrayList<Integer[]> intervals) {
        if (intervals.size() == 0) {
            return 0;
        }

        intervals.sort((a, b) -> a[0] - b[0]); // 升序排序

        int n = intervals.size();
        int[] f = new int[n]; // 数组记录第i个区间元素可以达到的最大不相交区间的个数
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals.get(j)[1] < intervals.get(i)[0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }
}